/**
 * 两种操作，强制在线
 * 1. u v： 连接u和v，保证任意时刻都是森林
 * 2. u v： 问是u和v是否存在共同的邻居，显然最多有一个
 * 
 * 对于操作2，如果不改变树的形态，一共只有三种情况，令答案记作x，则
 * u-x-v, v-x-u, 或者 x是u、v的直接父节点
 * 因此要维护父节点。
 * 
 * 但是操作1至少会改变一个树的形态，如何处理？
 * 将小树挂在大树上，然后暴力的更新小树的所有节点的父亲。
 * 整个合并操作可以控制在O(NlogN)完成。不会证。
 * 
 * 用并查集维护一下size即可。59ms。要优于LCT的91ms。同时代码大大简化。
 */
#include <bits/stdc++.h>
#include <bits/extc++.h>
using namespace std;

using llt = long long;
llt const MOD = 998244353;

struct uf_t{
vector<int> father;
vector<int> sz;
void init(int n){father.assign(n+1, 0);sz.assign(n+1,1);for(int i=1;i<=n;++i)father[i]=i;}
int find(int x){return x==father[x] ? x : father[x] = find(father[x]);}
void unite(int x, int y){
    x = find(x), y = find(y);
    father[y] = x;
    sz[x] += sz[y];
}
}U;

vector<int> Parent;
vector<vector<int>> G;

int N, Q;

void dfs(int u, int p){
    Parent[u] = p;
    for(auto v : G[u]){
        if(v == p) continue;
        dfs(v, u);
    }
    return;
}

void work(){
    cin >> N >> Q;
    G.assign(N + 1, {});
    Parent.assign(N + 1, 0);
    U.init(N);

    llt x = 0;
    for(int q=1;q<=Q;++q){
        llt a, b, c; 
        cin >> a >> b >> c;
        a = 1 + a * (x + 1) % MOD % 2;
        b = 1 + b * (x + 1) % MOD % N;
        c = 1 + c * (x + 1) % MOD % N;
#ifndef ONLINE_JUDGE
        cout << q << ": " << a << " " << b << " " << c << endl;
#endif
        if(1 == a){
            int bb = U.find(b);
            int cc = U.find(c);
            if(U.sz[bb] < U.sz[cc]) {swap(bb, cc); swap(b, c);}
            U.unite(b, c);

            G[b].push_back(c);
            G[c].push_back(b);
            dfs(c, b);
        }else{
            x = 0;
            if(U.find(b) == U.find(c)){
                if(Parent[b] == Parent[c]){
                    x = Parent[b];
                }else if(Parent[b] and Parent[Parent[b]] == c){
                    x = Parent[b];
                }else if(Parent[c] and Parent[Parent[c]] == b){
                    x = Parent[c];
                }
            }
            cout << x << "\n";
        }
    }
    return;
}

int main(){
#ifndef ONLINE_JUDGE
    freopen("z.txt", "r", stdin);
#endif
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int nofkase = 1;
    // cin >> nofkase;
    while(nofkase--) work();
    return 0;
}